import java.util.Arrays;

class Solution2 {
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int cur1 = 0, cur2 = 0;
        int ret = Integer.MIN_VALUE;
        int m = buses.length, n = passengers.length;

        // 遍历每一辆公交车
        for (int i = 0; i < m; i++) {
            int cap = 0; // 当前车的已载乘客数量

            // 当前车尽可能装满，且只能载在当前车发车之前到达的乘客
            while (cur2 < n && passengers[cur2] <= buses[i] && cap < capacity) {
                if (cur2 == 0 || passengers[cur2] != passengers[cur2 - 1] + 1) {
                    ret = passengers[cur2] - 1; // 找到可能的最晚时间
                }
                cur2++;
                cap++;
            }

            // 如果当前车还没满，可以考虑在发车时间之前赶上
            if (cap < capacity && (cur2 == 0 || passengers[cur2 - 1] != buses[i])) {
                ret = buses[i]; // 更新为当前车的发车时间
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        // 测试数据
        int[] buses = {10, 20};
        int[] passengers = {2, 17, 18, 19};
        int capacity = 2;

        Solution2 solution = new Solution2();
        int result = solution.latestTimeCatchTheBus(buses, passengers, capacity);

        // 输出测试结果
        System.out.println("Latest time to catch the bus: " + result);
    }
}